package kyssion.leetcode.num51_100;

public class code96_不同的二叉搜索树 {
    public static void main(String[] args) {
        System.out.println(new code96_不同的二叉搜索树().numTrees(19));
    }

    static int[][] dp;

    public int numTrees(int n) {
        dp = new int[n + 2][n + 2];
        return ans(1, n);
    }

    private int ans(int start, int end) {
        if (start >= end) {
            dp[start][end]=1;
            return 1;
        }
        int all = 0;
        for (int a = start; a <= end; a++) {
            int left = dp[start][a - 1] == 0 ? ans(start, a - 1) : dp[start][a - 1];
            int right = dp[a + 1][end] == 0 ? ans(a + 1, end) : dp[a + 1][end];
            all += left * right;
        }
        dp[start][end]=all;
        return all;
    }

    /**
     * 这个地推公式中有一个关键的地方就是,其实我们可以忽略掉位置的
     * f(3) 和当前x所处的位置无关,无论是 1-3 还是2-5 他们的数量是相同的
     * 由此就可以得到公式 fn = f(n-1)*f(0)+f(n-2)*f(1)+f(n-3)*f(3)...f(0)*f(n-1)
     * @param n
     * @return
     */
    public int numTrees2(int n) {
        //f(n)=f(n-1)*f(0)+f(n-2)*f(1)+f(n-3)*f(3)...f(0)*f(n-1)
        int[] nums=new int[n+1];
        nums[0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                nums[i]=nums[i]+nums[i-1-j]*nums[j];
            }
        }
        return nums[n];
    }
}
